模拟赛题解/2025.9.9 模拟赛

T1-图（graph）

题面

给定一个含有 $n$ 个节点和 $2n$ 条边的有向图，每个节点恰有两条出边和两条入边。

删去 $n$ 条边，使每个节点恰好还有 $1$ 条入边和 $1$ 条出边。

求删边的方案数，对 $998244353$ 取模。

$1\leq n\leq 10^5$。

题解

首先，原题的条件可以转化为每条边的两条出边不能同时删除，入边不能同时删除。

将边转化为点，在互斥的两条边之间连边，则原题条件就被转化为了求图上的最大独立集。

因为新图中只有偶环，所以可以直接将答案表示为 $2^{\text{偶环数}}$，并查集维护即可。

T2-树（tree）

题面

有一棵 $n$ 个节点的树，每条边的边权为 $c_i$。

你要从 $s$ 走到 $t$，一开始有体力 $k$，每次经过一条边 $i$ 体力就会减少 $c_i$。

如果体力变得不超过零，则会将体力恢复到 $k$。

问最后一共会恢复几次。

$2\leq n\leq 10^5,1\leq k\leq 10^9,0\leq c_i\leq 10^9,1\leq q\leq2\times10^5,s\not=t$。

题解

可以使用树链剖分+链上倍增的方法，复杂度 $O(n\log^2n)$，但有 $\text{TLE}$ 风险。

容易发现如果只考虑朝上走，就是求出每个点可以走到的点，接下来就是一个简单的倍增。

接下来考虑往下走的一段。这里有一个神秘的观察，对于一条链，如果体力都是满的从两边开始走，那么复活的次数是一样的。

考虑组合意义：这个等价于将整条序列分成尽量少的段，使得每一段之和都 $\geq k$，所以从两边开始贪心都是对的。

所以可以找到拐下去的点之后，从下往上倍增。

T3-团（clique）

题面

给定无向图 $G=(V,E)$，$V=\{1,2,\cdots,n\}$。

对每个顶点 $v$ 给定权值 $f_x(v),f_y(v)$。

边 $(i,j)\in E$ 当且仅当 $|f_x(i)-f_x(j)|-|f_y(i)-f_y(j)|\leq d$。

求 $G$ 的最大团的顶点数。

$1\leq n\leq 3\times 10^5,1\leq d,f_x(i),f_y(i)\leq 10^8$。

题解

观察到题面实际上就是两点之间的曼哈顿距离，显然不好维护，可以转化成切比雪夫距离。

因此题面就转化为在平面直角坐标系中一个边长为 $d$ 的正方形最多能覆盖多少个点。

可以用扫描线维护，复杂度 $O(n\log n)$。

T4-序列（sequence）

题面

有一个序列 $a_1,a_2\cdots,a_n$。记 $p_i$ 为前缀最大值。

定义一个序列是好的当且仅当：

• $\forall i(1\leq i\leq n),1\leq a_i\leq n$。
• $\forall i(1\leq i\leq n),p_i\leq p_{i-1}+1$。

对于 $1,2,\cdots,n$ 的所有数，求在所有好的序列中出现次数的平方总和是多少，对 $998244353$ 取模。

$1\leq n\leq 3000,1\leq m\leq 10^9$。

题解

首先可以把平方看成可重复地选择两个数字，那么对于 $k$，考虑 $f_{i,j,0\sim2}$ 表示前 $i$ 个数，当前最大值为 $j$，选了多少次的方案。

转移可以选择每次要不要增大 $j$，并且选择几次，当 $j<k$ 和 $j\geq k$ 时，考虑两种不同的转移，直接 $\text{dp}$ 的复杂度为 $O(n^3)$。

当 $k$ 不同时，可以发现前后两种情况的转移是分别相同的，即只有变化点不同。

考虑预处理前缀和后缀的转移，然后枚举断点，将前后方案数相乘即可。